Search Results

Documents authored by Herlihy, Maurice

Document
DOI: 10.4230/OASIcs.Tokenomics.2021.13
Presentation and Publication: Loss and Slippage in Networks of Automated Market Makers

Authors: Daniel Engel and Maurice Herlihy

Published in: OASIcs, Volume 97, 3rd International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2021)

Abstract
Automated market makers (AMMs) are smart contracts that automatically trade electronic assets according to a mathematical formula. This paper investigates how an AMM’s formula affects the interests of liquidity providers, who endow the AMM with assets, and traders, who exchange one asset for another at the AMM’s rates. Linear slippage measures how a trade’s size affects the trader’s return, angular slippage measures how a trade’s size affects the subsequent market price, divergence loss measures the opportunity cost of providers' investments, and load balances the costs to traders and providers. We give formal definitions for these costs, show that they obey certain conservation laws: these costs can be shifted around but never fully eliminated. We analyze how these costs behave under composition, when simple individual AMMs are linked to form more complex networks of AMMs.
Cite as

Daniel Engel and Maurice Herlihy. Presentation and Publication: Loss and Slippage in Networks of Automated Market Makers. In 3rd International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2021). Open Access Series in Informatics (OASIcs), Volume 97, pp. 13:1-13:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{engel_et_al:OASIcs.Tokenomics.2021.13,
  author =	{Engel, Daniel and Herlihy, Maurice},
  title =	{{Presentation and Publication: Loss and Slippage in Networks of Automated Market Makers}},
  booktitle =	{3rd International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2021)},
  pages =	{13:1--13:23},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-220-4},
  ISSN =	{2190-6807},
  year =	{2022},
  volume =	{97},
  editor =	{Gramoli, Vincent and Halaburda, Hanna and Pass, Rafael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.Tokenomics.2021.13},
  URN =		{urn:nbn:de:0030-drops-159103},
  doi =		{10.4230/OASIcs.Tokenomics.2021.13},
  annote =	{Keywords: Decentralized Finance, AMM, Uniswap}
}
Document
DOI: 10.4230/LIPIcs.DISC.2021.35
VBR: Version Based Reclamation

Authors: Gali Sheffi, Maurice Herlihy, and Erez Petrank

Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)

Abstract
Safe lock-free memory reclamation is a difficult problem. Existing solutions follow three basic methods (or their combinations): epoch based reclamation, hazard pointers, and optimistic reclamation. Epoch-based methods are fast, but do not guarantee lock-freedom. Hazard pointer solutions are lock-free but typically do not provide high performance. Optimistic methods are lock-free and fast, but previous optimistic methods did not go all the way. While reads were executed optimistically, writes were protected by hazard pointers. In this work we present a new reclamation scheme called version based reclamation (VBR), which provides a full optimistic solution to lock-free memory reclamation, obtaining lock-freedom and high efficiency. Speculative execution is known as a fundamental tool for improving performance in various areas of computer science, and indeed evaluation with a lock-free linked-list, hash-table and skip-list shows that VBR outperforms state-of-the-art existing solutions.
Cite as

Gali Sheffi, Maurice Herlihy, and Erez Petrank. VBR: Version Based Reclamation. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 35:1-35:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{sheffi_et_al:LIPIcs.DISC.2021.35,
  author =	{Sheffi, Gali and Herlihy, Maurice and Petrank, Erez},
  title =	{{VBR: Version Based Reclamation}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{35:1--35:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.35},
  URN =		{urn:nbn:de:0030-drops-148374},
  doi =		{10.4230/LIPIcs.DISC.2021.35},
  annote =	{Keywords: Safe memory reclamation, concurrency, linearizability, lock-freedom}
}
Document
Complete Volume
DOI: 10.4230/OASIcs.Tokenomics.2019
OASIcs, Vol. 71, Tokenomics 2019, Complete Volume

Authors: Vincent Danos, Maurice Herlihy, Maria Potop-Butucaru, Julien Prat, and Sara Tucci-Piergiovanni

Published in: OASIcs, Volume 71, International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2019)

Abstract
OASIcs, Vol. 71, Tokenomics 2019, Complete Volume
Cite as

International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2019). Open Access Series in Informatics (OASIcs), Volume 71, pp. 1-192, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@Proceedings{danos_et_al:OASIcs.Tokenomics.2019,
  title =	{{OASIcs, Vol. 71, Tokenomics 2019, Complete Volume}},
  booktitle =	{International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2019)},
  pages =	{1--192},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-108-5},
  ISSN =	{2190-6807},
  year =	{2020},
  volume =	{71},
  editor =	{Danos, Vincent and Herlihy, Maurice and Potop-Butucaru, Maria and Prat, Julien and Tucci-Piergiovanni, Sara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.Tokenomics.2019},
  URN =		{urn:nbn:de:0030-drops-119634},
  doi =		{10.4230/OASIcs.Tokenomics.2019},
  annote =	{Keywords: OASIcs, Vol. 71, Tokenomics 2019, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/OASIcs.Tokenomics.2019.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Vincent Danos, Maurice Herlihy, Maria Potop-Butucaru, Julien Prat, and Sara Tucci-Piergiovanni

Published in: OASIcs, Volume 71, International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2019)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2019). Open Access Series in Informatics (OASIcs), Volume 71, pp. 0:i-0:xii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{danos_et_al:OASIcs.Tokenomics.2019.0,
  author =	{Danos, Vincent and Herlihy, Maurice and Potop-Butucaru, Maria and Prat, Julien and Tucci-Piergiovanni, Sara},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2019)},
  pages =	{0:i--0:xii},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-108-5},
  ISSN =	{2190-6807},
  year =	{2020},
  volume =	{71},
  editor =	{Danos, Vincent and Herlihy, Maurice and Potop-Butucaru, Maria and Prat, Julien and Tucci-Piergiovanni, Sara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.Tokenomics.2019.0},
  URN =		{urn:nbn:de:0030-drops-119640},
  doi =		{10.4230/OASIcs.Tokenomics.2019.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/OASIcs.Tokenomics.2019.4
An Empirical Study of Speculative Concurrency in Ethereum Smart Contracts

Authors: Vikram Saraph and Maurice Herlihy

Published in: OASIcs, Volume 71, International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2019)

Abstract
We use historical data to estimate the potential benefit of speculative techniques for executing Ethereum smart contracts in parallel. We replay transaction traces of sampled blocks from the Ethereum blockchain over time, using a simple speculative execution engine. In this engine, miners attempt to execute all transactions in a block in parallel, rolling back those that cause data conflicts. Aborted transactions are then executed sequentially. Validators execute the same schedule as miners. We find that our speculative technique yields estimated speed-ups starting at about 8-fold in 2016, declining to about 2-fold at the end of 2017, where speed-up is measured using either gas costs or instruction counts. We also observe that a small set of contracts are responsible for many data conflicts resulting from speculative concurrent execution.
Cite as

Vikram Saraph and Maurice Herlihy. An Empirical Study of Speculative Concurrency in Ethereum Smart Contracts. In International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2019). Open Access Series in Informatics (OASIcs), Volume 71, pp. 4:1-4:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{saraph_et_al:OASIcs.Tokenomics.2019.4,
  author =	{Saraph, Vikram and Herlihy, Maurice},
  title =	{{An Empirical Study of Speculative Concurrency in Ethereum Smart Contracts}},
  booktitle =	{International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2019)},
  pages =	{4:1--4:15},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-108-5},
  ISSN =	{2190-6807},
  year =	{2020},
  volume =	{71},
  editor =	{Danos, Vincent and Herlihy, Maurice and Potop-Butucaru, Maria and Prat, Julien and Tucci-Piergiovanni, Sara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.Tokenomics.2019.4},
  URN =		{urn:nbn:de:0030-drops-119684},
  doi =		{10.4230/OASIcs.Tokenomics.2019.4},
  annote =	{Keywords: Blockchains, Smart Contracts}
}
Document
DOI: 10.4230/DagRep.7.11.1
New Challenges in Parallelism (Dagstuhl Seminar 17451)

Authors: Annette Bieniusa, Hans-J. Boehm, Maurice Herlihy, and Erez Petrank

Published in: Dagstuhl Reports, Volume 7, Issue 11 (2018)

Abstract
A continuing goal of current multiprocessor software design is to improve the performance and reliability of parallel algorithms. Parallel programming has traditionally been attacked from widely different angles by different groups of people: Hardware designers designing instruction sets, programming language designers designing languages and library interfaces, and theoreticians developing models of parallel computation. Unsurprisingly, this has not always led to consistent results. Newly developing areas show every sign of leading to similar divergence. This Dagstuhl Seminar will bring together researchers and practitioners from all three areas to discuss and reconcile thoughts on these challenges.
Cite as

Annette Bieniusa, Hans-J. Boehm, Maurice Herlihy, and Erez Petrank. New Challenges in Parallelism (Dagstuhl Seminar 17451). In Dagstuhl Reports, Volume 7, Issue 11, pp. 1-27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@Article{bieniusa_et_al:DagRep.7.11.1,
  author =	{Bieniusa, Annette and Boehm, Hans-J. and Herlihy, Maurice and Petrank, Erez},
  title =	{{New Challenges in Parallelism (Dagstuhl Seminar 17451)}},
  pages =	{1--27},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2018},
  volume =	{7},
  number =	{11},
  editor =	{Bieniusa, Annette and Boehm, Hans-J. and Herlihy, Maurice and Petrank, Erez},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.7.11.1},
  URN =		{urn:nbn:de:0030-drops-86681},
  doi =		{10.4230/DagRep.7.11.1},
  annote =	{Keywords: concurrency, memory models, non-volatile memory}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2017.10
The Teleportation Design Pattern for Hardware Transactional Memory

Authors: Nachshon Cohen, Maurice Herlihy, Erez Petrank, and Elias Wald

Published in: LIPIcs, Volume 95, 21st International Conference on Principles of Distributed Systems (OPODIS 2017)

Abstract
We identify a design pattern for concurrent data structures, called teleportation, that uses best- effort hardware transactional memory to speed up certain kinds of legacy concurrent data struc- tures. Teleportation unifies and explains several existing data structure designs, and it serves as the basis for novel approaches to reducing the memory traffic associated with fine-grained locking, and with hazard pointer management for memory reclamation.
Cite as

Nachshon Cohen, Maurice Herlihy, Erez Petrank, and Elias Wald. The Teleportation Design Pattern for Hardware Transactional Memory. In 21st International Conference on Principles of Distributed Systems (OPODIS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 95, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{cohen_et_al:LIPIcs.OPODIS.2017.10,
  author =	{Cohen, Nachshon and Herlihy, Maurice and Petrank, Erez and Wald, Elias},
  title =	{{The Teleportation Design Pattern for Hardware Transactional Memory}},
  booktitle =	{21st International Conference on Principles of Distributed Systems (OPODIS 2017)},
  pages =	{10:1--10:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-061-3},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{95},
  editor =	{Aspnes, James and Bessani, Alysson and Felber, Pascal and Leit\~{a}o, Jo\~{a}o},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2017.10},
  URN =		{urn:nbn:de:0030-drops-86306},
  doi =		{10.4230/LIPIcs.OPODIS.2017.10},
  annote =	{Keywords: Hardware transactional memory, concurrent data structures}
}
Document
DOI: 10.4230/LIPIcs.DISC.2017.35
Tight Bounds for Connectivity and Set Agreement in Byzantine Synchronous Systems

Authors: Hammurabi Mendes and Maurice Herlihy

Published in: LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017)

Abstract
In this paper, we show that the protocol complex of a Byzantine synchronous system can remain (k-1)-connected for up to ceil(t/k) rounds, where t is the maximum number of Byzantine processes, and t >= k >= 1. This topological property implies that ceil(t/k) + 1 rounds are necessary to solve k-set agreement in Byzantine synchronous systems, compared to floor(t/k) + 1 rounds in synchronous crash-failure systems. We also show that our connectivity bound is tight as we indicate solutions to Byzantine k-set agreement in exactly ceil(t/k) + 1 synchronous rounds, at least when n is suitably large compared to t. In conclusion, we see how Byzantine failures can potentially require one extra round to solve k-set agreement, and, for n suitably large compared to t, at most that.
Cite as

Hammurabi Mendes and Maurice Herlihy. Tight Bounds for Connectivity and Set Agreement in Byzantine Synchronous Systems. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 35:1-35:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{mendes_et_al:LIPIcs.DISC.2017.35,
  author =	{Mendes, Hammurabi and Herlihy, Maurice},
  title =	{{Tight Bounds for Connectivity and Set Agreement in Byzantine Synchronous Systems}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{35:1--35:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-053-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{91},
  editor =	{Richa, Andr\'{e}a},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.35},
  URN =		{urn:nbn:de:0030-drops-79930},
  doi =		{10.4230/LIPIcs.DISC.2017.35},
  annote =	{Keywords: Byzantine, synchronous, k-set agreement, topology, connectivity}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2017.50
Brief Announcement: A Persistent Lock-Free Queue for Non-Volatile Memory

Authors: Michal Friedman, Maurice Herlihy, Virendra Marathe, and Erez Petrank

Published in: LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017)

Abstract
Non-volatile memory is expected to coexist with (or even displace) volatile DRAM for main memory in upcoming architectures. As a result, there is increasing interest in the problem of designing and specifying durable data structures that can recover from system crashes. Data-structures may be designed to satisfy stricter or weaker durability guarantees to provide a balance between the strength of the provided guarantees and performance overhead. This paper proposes three novel implementations of a concurrent lock-free queue. These implementations illustrate the algorithmic challenges in building persistent lock-free data structures with different levels of durability guarantees. We believe that by presenting these challenges, along with the proposed algorithmic designs, and the possible levels of durability guarantees, we can shed light on avenues for building a wide variety of durable data structures. We implemented the various designs and evaluate their performance overhead compared to a simple queue design for standard (volatile) memory.
Cite as

Michal Friedman, Maurice Herlihy, Virendra Marathe, and Erez Petrank. Brief Announcement: A Persistent Lock-Free Queue for Non-Volatile Memory. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 50:1-50:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{friedman_et_al:LIPIcs.DISC.2017.50,
  author =	{Friedman, Michal and Herlihy, Maurice and Marathe, Virendra and Petrank, Erez},
  title =	{{Brief Announcement: A Persistent Lock-Free Queue for Non-Volatile Memory}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{50:1--50:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-053-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{91},
  editor =	{Richa, Andr\'{e}a},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.50},
  URN =		{urn:nbn:de:0030-drops-79689},
  doi =		{10.4230/LIPIcs.DISC.2017.50},
  annote =	{Keywords: Non-volatile Memory, Concurrent Data Structures, Non-blocking, Lock-free}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2015.13
The Relative Power of Composite Loop Agreement Tasks

Authors: Vikram Saraph and Maurice Herlihy

Published in: LIPIcs, Volume 46, 19th International Conference on Principles of Distributed Systems (OPODIS 2015)

Abstract
Loop agreement is a family of distributed tasks that includes set agreement and simplex agreement, and was used to prove the undecidability of wait-free solvability of distributed tasks by read/write memory. Herlihy and Rajsbaum defined the algebraic signature of a loop agreement task, which consists of a group and a distinguished element. They used the algebraic signature to characterize the relative power of loop agreement tasks. In particular, they showed that one task implements another exactly when there is a homomorphism between their respective signatures sending one loop to the other. In this paper, we extend the previous result by defining the composition of multiple loop agreement tasks to create a new one with the same combined power. We generalize the original algebraic characterization for relative power to compositions of tasks. In this way, we can think of loop agreement tasks in terms of their basic building blocks. We also investigate a category-theoretic perspective of loop agreement by defining a category of loops, showing that the algebraic signature is a functor, and proving that our definition of task composition is the "correct" one, in a categorical sense.
Cite as

Vikram Saraph and Maurice Herlihy. The Relative Power of Composite Loop Agreement Tasks. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 13:1-13:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{saraph_et_al:LIPIcs.OPODIS.2015.13,
  author =	{Saraph, Vikram and Herlihy, Maurice},
  title =	{{The Relative Power of Composite Loop Agreement Tasks}},
  booktitle =	{19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
  pages =	{13:1--13:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-98-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{46},
  editor =	{Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.13},
  URN =		{urn:nbn:de:0030-drops-66044},
  doi =		{10.4230/LIPIcs.OPODIS.2015.13},
  annote =	{Keywords: Distributed computing, loop agreement, task composition, topology}
}
Document
DOI: 10.4230/DagRep.2.3.50
Applications of Combinatorial Topology to Computer Science (Dagstuhl Seminar 12121)

Authors: Lisbeth Fajstrup, Dmitry Feichtner-Kozlov, and Maurice Herlihy

Published in: Dagstuhl Reports, Volume 2, Issue 3 (2012)

Abstract
This report documents the program of Dagstuhl Seminar 12121 "Applications of Combinatorial Topology to Computer Science". The seminar brought together researchers working on applications of combinatorial topology to various fields of computer science. The goal was to foster communication across these fields by providing researchers in each field the opportunity to explain their research programs to the others. The fields covered included distributed computing, persistent homology, semantics of concurrency, and sensor networks.
Cite as

Lisbeth Fajstrup, Dmitry Feichtner-Kozlov, and Maurice Herlihy. Applications of Combinatorial Topology to Computer Science (Dagstuhl Seminar 12121). In Dagstuhl Reports, Volume 2, Issue 3, pp. 50-66, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@Article{fajstrup_et_al:DagRep.2.3.50,
  author =	{Fajstrup, Lisbeth and Feichtner-Kozlov, Dmitry and Herlihy, Maurice},
  title =	{{Applications of Combinatorial Topology to Computer Science (Dagstuhl Seminar 12121)}},
  pages =	{50--66},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2012},
  volume =	{2},
  number =	{3},
  editor =	{Fajstrup, Lisbeth and Feichtner-Kozlov, Dmitry and Herlihy, Maurice},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.2.3.50},
  URN =		{urn:nbn:de:0030-drops-35363},
  doi =		{10.4230/DagRep.2.3.50},
  annote =	{Keywords: Combinatorial topology, Distributed computing, Persistent homology, Program semantics, Sensor networks}
}
Document
DOI: 10.4230/DagSemProc.08241.1
08241 Abstracts Collection – Transactional Memory : From Implementation to Application

Authors: Christof Fetzer, Tim Harris, Maurice Herlihy, and Nir Shavit

Published in: Dagstuhl Seminar Proceedings, Volume 8241, Transactional Memory : From Implementation to Application (2008)

Abstract
From 08.06. to 13.06.2008, the Dagstuhl Seminar 08241 ``Transactional Memory: From Implementation to Application'' was held in Schloss Dagstuhl – Leibniz Center for Informatics. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Christof Fetzer, Tim Harris, Maurice Herlihy, and Nir Shavit. 08241 Abstracts Collection – Transactional Memory : From Implementation to Application. In Transactional Memory : From Implementation to Application. Dagstuhl Seminar Proceedings, Volume 8241, pp. 1-13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{fetzer_et_al:DagSemProc.08241.1,
  author =	{Fetzer, Christof and Harris, Tim and Herlihy, Maurice and Shavit, Nir},
  title =	{{08241 Abstracts Collection – Transactional Memory : From Implementation to Application}},
  booktitle =	{Transactional Memory : From Implementation to Application},
  pages =	{1--13},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8241},
  editor =	{Christof Fetzer and Tim Harris and Maurice Herlihy and Nir Shavit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08241.1},
  URN =		{urn:nbn:de:0030-drops-17757},
  doi =		{10.4230/DagSemProc.08241.1},
  annote =	{Keywords: Multiprocessors, Multi-core machines, Concurrent Programming, Parallel Programming, Synchronization, Transactional Memory}
}
Document
DOI: 10.4230/DagSemProc.08241.2
08241 Summary – Transactional Memory : From Implementation to Application

Authors: Christof Fetzer, Tim Harris, Maurice Herlihy, and Nir Shavit

Published in: Dagstuhl Seminar Proceedings, Volume 8241, Transactional Memory : From Implementation to Application (2008)

Abstract
A goal of current multiprocessor software design is to introduce parallelism into software applications by allowing operations that do not conflict in accessing memory to proceed concurrently. The key tool in designing concurrent data structures has been the use of locks. Unfortunately, course grained locking is easy to program with, but provides very poor performance because of limited parallelism. Fine-grained lock-based concurrent data structures perform exceptionally well, but designing them has long been recognized as a difficult task better left to experts. If concurrent programming is to become ubiquitous, researchers agree that one must develop alternative approaches that simplify code design and verification.
Cite as

Christof Fetzer, Tim Harris, Maurice Herlihy, and Nir Shavit. 08241 Summary – Transactional Memory : From Implementation to Application. In Transactional Memory : From Implementation to Application. Dagstuhl Seminar Proceedings, Volume 8241, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{fetzer_et_al:DagSemProc.08241.2,
  author =	{Fetzer, Christof and Harris, Tim and Herlihy, Maurice and Shavit, Nir},
  title =	{{08241 Summary – Transactional Memory : From Implementation to Application}},
  booktitle =	{Transactional Memory : From Implementation to Application},
  pages =	{1--3},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8241},
  editor =	{Christof Fetzer and Tim Harris and Maurice Herlihy and Nir Shavit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08241.2},
  URN =		{urn:nbn:de:0030-drops-17741},
  doi =		{10.4230/DagSemProc.08241.2},
  annote =	{Keywords: Multiprocessors, Multi-core machines, Concurrent Programming, Parallel Programming, Synchronization, Transactional Memory}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact